public class Rob {
    // leetcode 打家劫舍
    // https://leetcode.cn/problems/house-robber/description/?envType=study-plan-v2&envId=top-100-liked
    public int rob(int[] nums) {
        // dp[0][i]表示当前房不偷时候的最高金额
        // dp[1][i]表示当前房偷时候的最大金额
        // dp[0][i] = Math.max(dp[1][i-1],dp[1][i-2]);
        // dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + nums[i];
        int n = nums.length;
        int[][] dp = new int[2][n+2];
        for (int i = 2; i < n+2; i++) {
            dp[0][i] = Math.max(dp[1][i-1],dp[1][i-2]);
            dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + nums[i-2];
        }
        return Math.max(dp[0][n+1],dp[1][n+1]);
    }
}
